package guide.贪心算法;

import java.util.Arrays;
import java.util.Comparator;

/**
 * <a href="https://leetcode-cn.com/problems/non-overlapping-intervals">435. 无重叠区间</a>
 * 给定多个区间，计算让这些区间互不重叠所需要移除区间的最少个数。起止相连不算重叠。
 * 示例 1：
 *  输入: [[1,2], [2,4], [1,3]]
 *  输出: 1
 *  解释：在这个样例中，我们可以移除区间 [1,3]，使得剩余的区间 [[1,2], [2,4]] 互不重叠。
 * @author 刘学松
 * @date 2021/2/15 18:26
 */
public class 移除最少重复区间 {
    public static void main(String[] args) {
        int[][] intervals = {{1, 2}, {2, 4}, {1, 3}};
        System.out.println(eraseOverlapIntervals(intervals));
    }

    public static int eraseOverlapIntervals(int[][] intervals) {
        if (intervals.length < 1) {
            return 0;
        }
        int length = intervals.length;
        Arrays.sort(intervals, Comparator.comparingInt(x -> x[1]));
        int count = 0;
        int tail = intervals[0][1];
        for (int i = 1; i < length; i++) {
            if (intervals[i][0] < tail) {
                ++count;
            } else {
                tail = intervals[i][1];
            }
        }
        return count;
    }
}
